package 字符串;

public class 计数二进制子串_696 {
/**
 * 给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。

	重复出现的子串要计算它们出现的次数。
	
	示例 1 :
	
	输入: "00110011"
	输出: 6
	解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。
	
	请注意，一些重复出现的子串要计算它们出现的次数。
	
	另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。
	示例 2 :
	
	输入: "10101"
	输出: 4
	解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。
 */
	//以“00111”为例，group={2,3}，当第一个1出现时，前面已经有2个0了，所以肯定能组成01；再遇到下一个1时，此时有2个0,2个1，所以肯定能组成0011；
	//再遇到下一个1时，前面只有2个0，而此时有3个1，所以不可以再组成满足条件的子串了。
	/*
	 * 
	 * 我们可以把一个字符串分组，来记录数字出现了多少次。 比如 00111  我们可以分成groups=[2,3]，  11110可以分成groups=[4,1].

		这样当最后计数的时候，对每一个值取min(groups[i-1], groups[i]).。
	
		这是为什么呢？  试想groups=[2,3]的情况，要么是00111要么是11000，无论是哪一种情况都只有 0011 、01或是1100、10两个子串符合条件，
		也就是groups中相邻两数的最小值。
	 */
	public int countBinarySubstrings(String s) {
		// pre 前一个数字连续出现的次数，cur 当前数字连续出现的次数，result 结果子串个数
		int preLen = 0, curLen = 1, ret = 0;
	    for(int i = 1; i < s.length(); i++){
	    	//相同,当前长度++
	        if(s.charAt(i) == s.charAt(i-1)) curLen++;
	        else{
	        	// 不同，则当前数字事实上变成了前一个数字，当前数字的次数重置为1
	            preLen = curLen;
	            curLen = 1;
	        }
	     // 前一个数字出现的次数 >= 后一个数字出现的次数，则一定包含满足条件的子串
	        if(preLen >= curLen) ret++;
	    }
	    return ret;
	}
}
